package com.duoduo.剑指Offer;

import com.duoduo.TreeNode;

/**
 * @program: algorithm
 * @description: 二叉搜索树的第k大节点33
 * 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: root = [3,1,4,null,2], k = 1
 * 3
 * / \
 * 1   4
 * \
 *    2
 * 输出: 4
 * @author: chaidl  ！
 * @create: 2022-05-26 22:13
 */
//TODO  这个是必须要掌握的
public class 二叉搜索树的第k大节点33 {
	int res, k;
	//此题其实是考察中序遍历，然后左跟右变为右根左就行
	public int kthLargest(TreeNode root, int k) {
		this.k = k;
		dfs(root);
		return res;
	}
	
	/**
	 * 采用广度优先的中序遍历倒序
	 *
	 * @param root
	 */
	private void dfs(TreeNode root) {
		if (root == null) {
			return;
		}
		//先从左右边的叶子结点遍历
		dfs(root.right);
		//如果k为0，表示已经找到了后续的遍历已变得毫无意义
		if (k == 0) {
			return;
		}
		// 当k=0的时候,将此时root节点的值返回
		if (--k == 0) {
			res = root.val;
		}
		dfs(root.left);
	}
}
